{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## deque - Double ended queues\n",
    "\n",
    "Using deque module, make queues that support adding and removing of elements from both the ends."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque:  deque(['h', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'd'])\n",
      "length:  10\n",
      "left end:  h\n",
      "right end:  d\n"
     ]
    }
   ],
   "source": [
    "# construction and initialisation\n",
    "\n",
    "import collections\n",
    "\n",
    "dq = collections.deque('helloworld')\n",
    "print('deque: ', dq)\n",
    "print('length: ', len(dq))\n",
    "print('left end: ', dq[0])\n",
    "print('right end: ', dq[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "After removal:  deque(['h', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'd'])\n"
     ]
    }
   ],
   "source": [
    "# removing elements from deque\n",
    "\n",
    "dq.remove('e')\n",
    "print('After removal: ', dq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a1 extend:  deque(['a', 'd', 'd', 'i', 'n', 'g', 't', 'h', 'i', 's', 't', 'o', 'r', 'i', 'g', 'h', 't'])\n",
      "a1 append:  deque(['a', 'd', 'd', 'i', 'n', 'g', 't', 'h', 'i', 's', 't', 'o', 'r', 'i', 'g', 'h', 't', 'somemore'])\n",
      "a2 extendleft:  deque(['t', 'f', 'e', 'l', 'o', 't', 'd', 'd', 'a'])\n",
      "a2 appendleft:  deque(['moretoleft', 't', 'f', 'e', 'l', 'o', 't', 'd', 'd', 'a'])\n"
     ]
    }
   ],
   "source": [
    "# Populating\n",
    "\n",
    "# Add to the right\n",
    "a1 = collections.deque()\n",
    "a1.extend('addingthistoright')\n",
    "print('a1 extend: ', a1)\n",
    "a1.append('somemore')\n",
    "print('a1 append: ', a1)\n",
    "\n",
    "\n",
    "# Add to the left\n",
    "a2 = collections.deque()\n",
    "a2.extendleft('addtoleft')\n",
    "print('a2 extendleft: ', a2)\n",
    "a2.appendleft('moretoleft')\n",
    "print('a2 appendleft: ', a2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "somemore\n",
      "a1 after right pop:  deque(['a', 'd', 'd', 'i', 'n', 'g', 't', 'h', 'i', 's', 't', 'o', 'r', 'i', 'g', 'h', 't'])\n",
      "\n",
      "a\n",
      "a2 after right pop:  deque(['moretoleft', 't', 'f', 'e', 'l', 'o', 't', 'd', 'd'])\n",
      "a\n",
      "a1 pop from left:  deque(['d', 'd', 'i', 'n', 'g', 't', 'h', 'i', 's', 't', 'o', 'r', 'i', 'g', 'h', 't'])\n",
      "\n",
      "moretoleft\n",
      "a2 pop from left:  deque(['t', 'f', 'e', 'l', 'o', 't', 'd', 'd'])\n"
     ]
    }
   ],
   "source": [
    "# Popping elements\n",
    "\n",
    "# from the right\n",
    "print(a1.pop())\n",
    "print('a1 after right pop: ', a1)\n",
    "print()\n",
    "print(a2.pop())\n",
    "print('a2 after right pop: ', a2)\n",
    "\n",
    "\n",
    "# from the left\n",
    "print(a1.popleft())\n",
    "print('a1 pop from left: ', a1)\n",
    "print()\n",
    "print(a2.popleft())\n",
    "print('a2 pop from left: ', a2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original deque:  deque([0, 1, 2, 3, 4, 5, 6])\n",
      "Right rotation:  deque([4, 5, 6, 0, 1, 2, 3])\n",
      "Left rotation:  deque([3, 4, 5, 6, 0, 1, 2])\n"
     ]
    }
   ],
   "source": [
    "# rotating deque\n",
    "\n",
    "b1 = collections.deque(range(7))\n",
    "\n",
    "print('Original deque: ', b1)\n",
    "\n",
    "# right rotate\n",
    "b2 = collections.deque(range(7))\n",
    "b2.rotate(3)\n",
    "print('Right rotation: ', b2)\n",
    "\n",
    "# left rotate\n",
    "b3 = collections.deque(range(7))\n",
    "b3.rotate(-3)\n",
    "print('Left rotation: ', b3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 iteration : deque currently containing values deque([0], maxlen=5)\n",
      "1 iteration : deque currently containing values deque([0, 1], maxlen=5)\n",
      "2 iteration : deque currently containing values deque([0, 1, 2], maxlen=5)\n",
      "3 iteration : deque currently containing values deque([0, 1, 2, 3], maxlen=5)\n",
      "4 iteration : deque currently containing values deque([0, 1, 2, 3, 4], maxlen=5)\n",
      "5 iteration : deque currently containing values deque([1, 2, 3, 4, 5], maxlen=5)\n",
      "6 iteration : deque currently containing values deque([2, 3, 4, 5, 6], maxlen=5)\n",
      "7 iteration : deque currently containing values deque([3, 4, 5, 6, 7], maxlen=5)\n",
      "8 iteration : deque currently containing values deque([4, 5, 6, 7, 8], maxlen=5)\n",
      "9 iteration : deque currently containing values deque([5, 6, 7, 8, 9], maxlen=5)\n"
     ]
    }
   ],
   "source": [
    "# Restricting deque size\n",
    "# At max the elements inserted are only upto the defined Q length. \n",
    "# All the previous elements are overwritten by the new elements.\n",
    "\n",
    "rsq = collections.deque(maxlen = 5)\n",
    "for i in range(10):\n",
    "    rsq.append(i)\n",
    "    print('{} iteration : deque currently containing values {}'.format(i, rsq))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
